package priv.pront.code.national.acwing.dp.bags;

import java.util.Scanner;

public class Acwing1020_潜水员 {

    static int N = 1010, M = 100;
    static int[][] f = new int[M][M];
    //氧气
    static int[] a = new int[N];
    //氮气
    static int[] b = new int[N];
    //重量
    static int[] w = new int[N];
    static int n, m, k;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 1; i <= k; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = 0x3f3f3f3f;
            }
        }
//        FIXME 为什么这里初始化0？
        f[0][0] = 0;
        //从前i个物品中选，氧气至少是j,氮气至少是l的最小重量
        for (int i = 1; i <= k; i++) {
            for (int j = n; j >= 0; j--) {
                for (int l = m; l >= 0; l--) {
                    f[j][l] = Math.min(f[j][l], f[Math.max(0, j - a[i])][Math.max(0, l - b[i])] + w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}
